\documentclass[a4paper,12pt]{article}

\usepackage[margin=1.5cm]{geometry}
\usepackage{fancyvrb}
\usepackage{url}

\title{Data Alignment in C}
\author{Chen Rushan\\chenrsster@gmail.com}
\date{2009.08.15 00:55}

\setlength{\parskip}{1.2ex}
\setlength{\parindent}{0pt}

\begin{document}
\maketitle

\section{Some basic definitions}

   Some basic definitions are listed in the following table:
   \begin{center}
   \begin{tabular}{|p{4cm}|c|p{1.3cm}||c|p{8cm}|}
      \hline
      \multicolumn{3}{|c||}{\bfseries Concept} & \multicolumn{2}{c|}
      {\bfseries Condition}\\
      \hline \hline
      data & & aligned && it's stored at an address equal to some multiple of its
      size \\
      \cline{1-1}\cline{3-3}\cline{5-5}
      memory address & \bfseries is & n-byte aligned && n is a power of two and 
      the address is a multiple of n-bytes\\
      \cline{1-1}\cline{3-3}\cline{5-5}
      memory access & \bfseries said & aligned & \bfseries if & the datum being
      accessed is n bytes long and the datum address is n-byte aligned, otherwise,
      it's said to be {\em misaligned}\\
      \cline{1-1}\cline{3-3}\cline{5-5}
      memory pointer referring to primitive data that is n-byte long & \bfseries to 
      & aligned && it's only allowed to contain addresses that are n-byte aligned,
      otherwise, it's said to be {\em unaligned}\\
      \cline{1-1}\cline{3-3}\cline{5-5}
      memory pointer referring to data aggregate(struct or array) & \bfseries be &
      aligned && each primitive datum in the aggregate is aligned\\
      \hline
   \end{tabular}
   \end{center}

   There are something you need to note:
   \begin{itemize}
      \item 1 is also a power of 2, so datum of 1-byte long is always aligned.
      \item byte memory accesses are always aligned.
      \item the definitions above assume that each primitive datum is a power of two
      bytes long. When this is not the case (as with 80-bit floating-point on x86)
      the context influences the conditions where the datum is considered aligned or
      not.
   \end{itemize}
\section{Why alignment is needed?}
   A computer accesses memory one memory word at a time. Suppose your memory word
   is 4-byte long, and you now want to read a datum of 4-byte long from memory, if
   the address of this datum is not 4-byte aligned, then the datum access must be
   split into two memory accesses. This requires a lot of complex circuitry to
   generate the memory accesses and coordinate them, which is also much slower.

\section{Data structure alignment}
   To align a data structure, it may be necessary to insert some meaningless bytes,
   this is called {\em data structure padding}. These bytes may be inserted in two
   situations. In order for each element of the struct to be properly aligned, bytes
   may be padded after some elements, and in order for each struct in an array to be
   properly aligned bytes may be padded after each struct. Here we're mainly
   concerned with the first case.

   {\bfseries \em A general rule is that padding is only inserted when a structure
   member is followed by a member with a larger alignment requirement or at the end
   of the structure.}

\section{Some examples} 
   On Linux running on 32-bit Intel processor, the default alignment for the following 
   types are:
   \begin{itemize}
      \item A \verb=char= type is 1-byte aligned.
      \item A \verb=short= type is 2-byte aligned.
      \item An \verb=int= type is 4-byte aligned.
      \item A \verb=float= type is 4-byte aligned.
      \item A \verb=double= type is 4-byte aligned.
   \end{itemize}
   Note that a double type is 4-byte aligned by default, this can be changed by
   providing \verb=-malign-double= option to gcc if you want double to be 8-byte
   aligned.

   Now here comes some examples:

   For a struct as follows:
   \begin{Verbatim}[frame=single]
struct my_data {
        short data1;
        short data2;
        short data3;
};
   \end{Verbatim}

   Since there's no such elements that followed by a element with larger alignment
   requirement, the size of this struct after compilation is simply 3*2, that is 6,
   and \verb=data1= is at offset 0, \verb=data2= at offset 2, \verb=data3= at offset
   4.

   Now consider a somewhat complex struct as follows:
   \begin{Verbatim}[frame=single]
struct mixed_data {
        char c;
        short s;
        int i;
        char c2;
};
   \end{Verbatim}

   In order for \verb=s= to be aligned on a 2-byte boundary, a extra byte should be
   padded after \verb=c=, and after padding this byte, \verb=i= will be successfully
   aligned on a 4-byte boundary(sizeof(c) + 1 + sizeof(short) = 4). The final struct 
   after compilation would be:
   \begin{Verbatim}[frame=single]
struct mixed_data {
        char c;
        char padding0[1];
        short s;
        int i;
        char c2;
        char padding1[3];
};
   \end{Verbatim}

   Note that 3 extra bytes are padded after \verb=c2=, this is done in order to
   conform to the largest type of the struct. It's possible to decrease the amount of
   space needed, just change the position of \verb=c2= to be right after \verb=c=,
   then there will no padding needed for any of these members.

\section{Misc}
   \subsection{Alignment checking on Intel processor}
      By default, the alignment checking is disabled on Intel processor, so we're
      allowed to perform a misaligned read and write. In fact, you can enable this
      checking by adding the following asm code to your C program:
      \begin{Verbatim}[frame=single]
#if defined(__GNUC__)
# if defined(__i386__)
    /* Enable Alignment Checking on x86 */
    __asm__("pushf\norl $0x40000,(%esp)\npopf");
# elif defined(__x86_64__) 
     /* Enable Alignment Checking on x86_64 */
    __asm__("pushf\norl $0x40000,(%rsp)\npopf");
# endif
#endif
      \end{Verbatim}

      After that, if you still perform a misaligned read or write, your program
      will get a SIGBUS signal, which by default causes your program to abort
      abnormally.

   \subsection{double data type}
      From above, we know that double data is 4-byte aligned on Linux running on
      32-bit Intel processor, so for the following struct:
      \begin{Verbatim}[frame=single]
struct mixed_data {
        char c;
        short s;
        double d;
        char c2;
};
      \end{Verbatim}
      a total amount of 16 bytes space is used to store such a struct, but if you
      compile your program with \verb=-malign-double= option, then the space needed
      will become 24 bytes. In fact, compiling your program with that option
      will speed up the final binary, but at the expense of more memory consumption.

      But when double type is used as an individual datum, it seems that it's always
      aligned on a 8-byte boundary, which is slightly different than when it's used
      as part of a struct.

\section{References}
\begin{itemize}
   \item \url{http://en.wikipedia.org/wiki/Data_structure_alignment}
   \item \url{http://en.wikipedia.org/wiki/Bus_error}
   \item Expert C Programming
\end{itemize}
\end{document}
